package binarysearch;

import org.junit.Test;

import java.util.Arrays;

public class SearchInRotatedSortedArray33 {

    @Test
    public void test() {
        print(new int[]{2,1}, 1);
        print(new int[]{2,1}, 2);
        print(new int[]{3,4,5,1,2}, 5);
        print(new int[]{3,4,5,1,2}, 1);
        print(new int[]{3,4,5,1,2}, 3);
        print(new int[]{3,4,5,1,2}, 6);
        print(new int[]{3,4,5,1,2}, 0);
        print(new int[]{4,5,7,0,1,2}, 6);
        print(new int[]{4,5,7,0,1,2}, 8);
        print(new int[]{11,13,15,17}, 10);
        print(new int[]{11,13,15,17}, 18);
    }

    public void print(int[] nums, int target) {
        System.out.format("nums: %s, target: %d, index: %d\n", Arrays.toString(nums), target, search(nums, target));
    }

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while (left <= right) {
            int mid = (left + right)/2;
            if (nums[mid] == target) {
                return mid;
            }
            // 不能以left为基准, 必须以right为基准
            // 避免后面的 nums[right] <= target 这种情况出现. 比如[2, 1]中找1, 下面的if-else逻辑会有问题.
            if (nums[right] == target) {
                return right;
            }

            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else if (nums[mid] <= nums[right] && nums[right] < target) {
                right = mid - 1;
            } else if (nums[right] < target && target < nums[mid]) {
                right = mid - 1;
            } else if (nums[right] <= nums[mid] && nums[mid] < target) {
                left = mid + 1;
            } else if (target < nums[mid] && nums[mid] <= nums[right]) {
                right = mid - 1;
            } else if (target < nums[right] && nums[right] <= nums[mid]) {
                left = mid + 1;
            } else {
                throw new RuntimeException(String.format("mid: %d, right: %d, target: %d", mid, right, target));
            }
        }
        return -1;
    }
}
